package p200;

public class Leetcode_279 {
    /**
     * 任何正整数都可以拆分成不超过4个数的平方和 ---> 答案只可能是1,2,3,4
     * 如果一个数最少可以拆成4个数的平方和，则这个数还满足 n = (4^a)*(8b+7) ---> 因此可以先看这个数是否满足上述公式，如果不满足，答案就是1,2,3了
     * 如果这个数本来就是某个数的平方，那么答案就是1，否则答案就只剩2,3了
     * 如果答案是2，即n=a^2+b^2，那么我们可以枚举a，来验证，如果验证通过则答案是2
     * 只能是3
     *
     * @param n
     * @return
     */
    public int numSquares(int n) {
        while (0 == n % 4) {
            n /= 4;
        }
        if (7 == n % 8) {
            return 4;
        }
        for (int i = 0; i * i < n; i++) {
            int j = (int) Math.pow(n - i * i, 0.5);
            if (n == i * i + j * j) {
                int a = i > 0 ? 1 : 0;
                int b = j > 0 ? 1 : 0;
                return a + b;
            }
        }
        return 3;
    }

    public static void main(String[] args) {
        Leetcode_279 l = new Leetcode_279();
        System.out.println(l.numSquares(6));
    }
}
